在这章中我们将找出，通信信道使用$n$次后最大可分辨的信号量。这个数量随$n$指数增长，指数值叫做channel capacity.
信道的物理模型如图所示。
来自有限符号表的源符号倍映射成信道符号的序列，之后经过信道的输出序列被接收方接收。输出序列是随机的，但有一个由输入序列决定的概率分布。从输出信号中，我们尝试恢复传递的信息。

定义：定义无记忆的离散“信息”通道容量为：

$$C= \max _{p(x)} I(X;Y)$$

最大值取遍所有可能的输入分布$p(x)$

例子：
1.非重叠输出的噪声信道：

每个传输结果可以确定传输的内容，因此$C=\max I(X;Y)=1 bit$，当$p(x)=\left( \frac{1}{2}, \frac{1}{2} \right)$时取到。

2.noisy typewriter

$\max I(X;Y) = \max[H(Y)-H(Y|X)]=\max(H(Y))-1=\log 26-1 = \log 13$

3.二元对称信道：0有$1-p$概率保持0，$p$概率翻转为1，输入1同样.

$$I(X;Y)\leq 1-H(p)$$

4.二元擦除信道：0和1均有$\alpha$概率消失。

$$C = \max_{p(x)} I(X;Y) = \max_{p(x)} (H(Y)-H(Y|X))=\max_{p(x)} H(Y) -H(\alpha)$$

让$E$为事件$\{Y=e\}$，

$$H(Y) = H(Y,E) = H(E)+H(Y|E)$$

令$X=1$概率为$\pi$,于是

$$H(Y) = H((1-\pi)(1-\alpha),\alpha,\pi(1-\alpha))= H(\alpha)+(1-\alpha)H(\pi)$$

$$\begin{align} C & =\max _{p(x)} H(Y)-H(\alpha) \\ & = \max _{\pi}(1-\alpha)H(\pi) + H(\alpha) - H(\alpha) \\ & = \max _{\pi} (1-\alpha) H(\pi) \\ & = 1-\alpha \end{align}$$

5.对称信道：概率转移矩阵$p(y\mid x)$的每一行/列都是一组概率的排列。
例：
$Y=X+Z (\text{mod}\ c)$
$Z$分布在$0,1,\dots c-1$之间，X与Z有相同的字母表。
此时

$$I(X;Y) = H(Y)-H(Y|X)=H(Y)-H(\mathbf{r})\leq \log|\mathscr{Y}|-H(r)$$

当输入均匀分布时，输出也均匀分布，此时取得等号

弱对称信道：每一行都是一组概率的排列，例：

$$p(y|x) = \left( \begin{matrix} \frac{1}{3} & \frac{1}{6} & \frac{1}{2} \\ \frac{1}{3} & \frac{1}{2} & \frac{1}{6} \end{matrix} \right)$$

上述结论同样适用于弱对称信道。

性质：

1. $C\geq 0$
2. $C\leq \log |\mathscr{H}|$
3. $C\leq \log |\mathscr{ Y}|$
4. $I(X,Y)$ is continuous and concave function of $p(x)$

Channel coding theorem

信道编码定理给出了信道中信息传输的最大速率$R\leq C$。一个简单解释如下：

使用$n$次信道时，长度n的编码$X^n$构成了空间$\mathscr{X}^n$，发送的序列构成了空间$\mathscr{Y}^n$。考虑典型集的大小，$\mathscr{X}^n$中有$2^{nH(X)}$个元素,$\mathscr{Y}^n$中有$2^{nH(Y)}$个元素。给定一个$X^n$，传输后对应的典型集合大小为$2^{nH(Y|X)}$。为了防止混淆，我们应该使$\mathscr{Y}^n$中结果不相交，因此不能传输$\mathscr{X}^n$中所有元素。那么有多少元素可以被传输呢？作为估计，我们可以用$\mathscr{Y}^n$的大小除以每次传输的典型集大小，即：

$$2^{n(H(Y))-H(Y|X)}=2^{nI(X;Y)}$$

也就是说，有$2^{nI(X;Y)}$个序列是可以互相分辨的。从而传输信息量为$nI(X;Y)$，将这个数字平均到每次使用信道，并控制X的概率分布使其最大，于是得到结论：单次传输的平均信息量（亦即通信速率）最多为$\max_{p(x)}I(X;Y)=C$

(Channel coding theorem) for every rate $R<C$, there exists a sequence of $(2^{nR},n)$ codes with maximum probability of error $\lambda^{(n)}\to0$; Conversely, any sequence of $(2^{nR},n)$ codes with $\lambda^{(n)} \to 0$ must have $R\leq C$

Leave a Comment

Plain Markdown

Post Comment

Markdown Preview